Continuous tone photo-realistic still and moving images can be stored in digital form as matrices of quantized analog values. Each matrix is a two-dimensional matrix of individual picture elements or “pixels,” which each store a value representing a color or grayscale tone on an integer-based gradient scale. For example, a single 16-bit pixel value represents one color picked from a palette consisting of 216 or 65,536 individual colors. The number of available colors in the color palette is known as the color depth. The pixels for each image are stored into a file rendering the image at a set dimension, such as 640×480 pixels.
In raw uncompressed form, the size of a digital image file increases dramatically with the color depth and image dimensions. A richer color palette has more color values and a larger dimensioned image stores a proportionately increased number of pixels. Fortunately, digital image storage can benefit from data compression techniques which take advantage of repetitive or otherwise structured data to compress a digital image file to a smaller size. The Joint Photographic Expert Group (JPEG) file format is presently the most commonly used format for storing compressed photo-realistic digital image file data, and is described in G. K. Wallace, “The JPEG Still Picture Compression Standard,” Comm. of the ACM (April 1991), and W. B. Pennebaker et al., “JPEG Still Image Data Compression Standard,” Van Nostrad Rhinehold (1993), the disclosures of which are incorporated by reference.
Historically, hardware limitations have dictated the color depth of digital images. Early color graphics adapters supported a limited number of bits per pixel and consequently the maximum image size and color depth were device-dependent. The number of colors appearing in a digital image were thus limited and had to be reduced by mapping the colors to the palette available to the display device prior to display.
Increasingly, digital images are being exchanged between interconnected networks of computer systems, including over the Internet, as well as with lightweight clients, such as personal data assistants (PDAs) and cellular telephones. Typically, these devices offer display devices capable of providing a range of colors that push the very limits of visual perception.
The rich color depths afforded by these devices result in large file sizes. However, the ability to exchange data, including digital images, over a network, is limited in part by the network bandwidth available to each device. In turn, the available bandwidth is affected by the capabilities of and load upon the network infrastructure, as well as by the means by which each client is interconnected. Low bandwidth dictates longer download times for larger file sizes. A slow modem connection, for instance, has low bandwidth that restricts the ability of a client to download data. Low bandwidth is particularly problematic when receiving digital images as content embedded, for instance, in Web pages. A balance between color depth and file size is necessary to accommodate the bandwidth available to a requesting client.
One solution to resolving the low bandwidth problem is to apply color reduction to a digital image file. Decreasing the color density by using a smaller color palette decreases the file size. In basic color reduction, the color palette is reduced by combining closely-related colors. Colors in the original palette are mapped to a smaller color table as a form of “lossy” data compression, that is, a process that loses information upon compression. A certain degree of image-dependent color reduction can be applied without affecting visual perception. The minimal number of colors needed to represent a digital image without affecting visual perception is referred to as the natural color depth. Ideally, color reduction will reduce color depth close to the natural color depth.
In practice, natural color depth is difficult to achieve. The capabilities of the display device, lighting conditions, observer's eyesight and a myriad of similar factors affect the natural color depth of an image, such as described in R. C. Gonzalez et al., “Digital Image Processing,” pp. 21–28 (Addison-Wesley Pub. Co. 1992), the disclosure of which is incorporated by reference.
Two prior art approaches apply color reduction to digital images in an effort to reduce a digital image to a target number of colors while attempting to minimize perceptual error. The first prior art approach is performed manually by graphics artists who perform an ad hoc selection of individual colors on an image-by-image basis. The goal is to optimize the compression ratio of the image balanced against visual fidelity. Nevertheless, this approach results in inconsistent results and typically uses an unnecessarily large number of colors.
In the second prior art approach, conventional color reduction approaches attempt to map the colors used in an image to a target palette of colors at a predetermined color depth. Proximate colors are mapped based on intensity without considering visual area. This approach can cause undesirable visual artifacts and uses an unnecessarily large number of colors in maintaining an acceptable visual quality. As well, by basing color reduction on a predetermined color depth, conventional color reduction approaches fail to find a substantially minimum number of colors necessary to achieve the natural color depth.
Therefore, there is a need to an approach to reducing the number of colors in a digital image to a natural color depth. Such an approach would preferably result in the selection of a substantially minimum number of colors to thereby maximize the visual perception of the resulting color reduced image. Preferably, such an approach would work either alone or with other forms of color reduction.
There is a further need for an approach to performing automatic color reduction of digital images. Such an approach would preferably dynamically analyze the colors used in an image and substantially minimize the colors to render the image in a natural color depth.